package com.aqie.easy.binarySearchTree;

import com.aqie.easy.structure.TreeNode;

import java.util.ArrayList;

/**
 * @Function: 669. 修剪二叉搜索树
 * @Author: aqie
 * @Date: 2019/6/30 9:18
 * 中序遍历 : 左 -> 根 -> 右
 * list 转 int 数组
 */
public class TrimBST {
    ArrayList<Integer> list = new ArrayList<>();
    public TreeNode trimBST2(TreeNode root, int L, int R) {
        // 1. 获取指定范围内的二叉搜索树节点
       if (root == null) return null;
        traverseTree(root, L, R);
        // 2. 根据有序数组重新生成二叉搜索树
        return toBST(list.stream().mapToInt(Integer::valueOf).toArray(),0,list.size() - 1);
    }

    private void traverseTree(TreeNode root, int L, int R) {
        if (root != null) {
            traverseTree(root.left, L, R);
            if (root.val >= L && root.val <= R) {
                list.add(root.val);
            }
            traverseTree(root.right, L, R);
        }
    }
    private TreeNode toBST(int[] nums, int left, int right) {
        if(left > right) return null;
        int mid = left + ((right - left) >> 1);
        TreeNode root = new TreeNode(nums[mid]);
        root.left = toBST(nums, left, mid - 1);
        root.right = toBST(nums, mid + 1, right);
        return root;
    }


    /**
     * 真正剪枝 三种情况
     * root->val　< L, root及左枝剪掉，右枝提升为root;
     * L <= roor->val <= R, 正常修剪
     * root->val > R ,root及右枝剪掉，左枝提升为root.
     */
    public TreeNode trimBST(TreeNode root, int L, int R) {
        if (root == null) return null;
        if (root.val < L){
            root.left = null;
            root = trimBST(root.right, L, R);
            return root;
        } else if (root.val > R) {
            root.right = null;
            root = trimBST(root.left, L, R);
            return root;
        }else{
            root.left = trimBST(root.left, L, R);
            root.right = trimBST(root.right, L, R);
            return root;
        }
    }
}
